package 动态规划;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-13
 */
public class 求路径 {
    public static void main(String[] args) {
        System.out.println(uniquePaths(2, 2));
        System.out.println(uniquePathsRecur(1, 1));
    }

    /**
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public static int uniquePaths(int m, int n) {
        // write code here
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            memo[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            memo[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
            }
        }
        return memo[m - 1][n - 1];
    }

    static int[][] dp = new int[2][2];

    /**
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public static int uniquePathsRecur(int m, int n) {
        // write code here
        if (m == 0 || n == 0) {
            return 1;
        }
        if (dp[m][n] == 0) {
            dp[m][n] = uniquePathsRecur(m - 1, n) + uniquePathsRecur(m, n - 1);
        }
        return dp[m][n];
    }

}
